package nio;

import java.nio.ByteBuffer;

public class QuickSort<E extends Comparable<E>> {

	void quicksort(E[] src) {
		quicksort(src, 0, src.length - 1);
	}

	void quicksort(E[] src, int left, int right) {

		// need to stop
		if (left >= right) {
			return;
		}
		int pivot_index = partition(src, left, right);
		quicksort(src, left, pivot_index);
		quicksort(src, pivot_index + 1, right);

	}

	int partition(E[] src, int left, int right) {
		E pivot = src[(left + right) / 2];

		int i = left;
		int j = right;
		// the condition
		while (i <= j) {

			// the condition
			while (src[i].compareTo(pivot) < 0)
				i++;
			// the condition
			while (src[j].compareTo(pivot) > 0)
				j--;

			// the condition
			if (i <= j) {
				swap(src, i, j);

				// do this make sure, j will be smaller that i
				i++;
				j--;
			}
		}

		// need to return j, since j is smaller at last.
		return j;
	}

	void swap(E[] src, int left, int right) {

		E temp = src[left];
		src[left] = src[right];
		src[right] = temp;
	}

	public static void quick_sort(int[] data, int low, int high) { // 1 or 0
		// items are
		// sorted by default
		if (high - low < 1)
			return;

		int left = low;
		int right = high;
		int pivot = data[low + (high - low) / 2];

		while (left <= right) { // Increment left pointer until left >= pivot
			while (data[left] < pivot)
				left++;

			// Increment right pointer until right <= pivot
			while (data[right] > pivot)
				right--;

			// If left < right; swap values
			if (left <= right) {
				int temp = data[left];
				data[left] = data[right];
				data[right] = temp;
				left++;
				right--;
			}

		}
		// quick_sort 'lesser values'
		quick_sort(data, low, right);

		// quick_sort 'greater values'
		quick_sort(data, left, high);
	}

	public static void quick_sort(byte[] data, int left, int right) { // 1 or 0
		// items are
		// sorted by default
		if (right - left < 1)
			return;

		int i = left;
		int j = right;
		int pivot = data[left + (right - left) / 2];

		while (i <= j) { // Increment left pointer until left >= pivot
			while (data[i] < pivot)
				i++;

			// Increment right pointer until right <= pivot
			while (data[j] > pivot)
				j--;

			// If left < right; swap values
			if (i <= j) {
				byte temp = data[i];
				data[i] = data[j];
				data[j] = temp;
				i++;
				j--;
			}

		}
		// quick_sort 'lesser values'
		quick_sort(data, left, j);

		// quick_sort 'greater values'
		quick_sort(data, i, right);
	}
	
	public static void quick_sort(ByteBuffer data, int left, int right) { // 1 or 0
		// items are
		// sorted by default
		if (right - left < 1)
			return;

		int i = left;
		int j = right;
		byte pivot = data.get(left + (right - left) / 2);

		while (i <= j) { // Increment left pointer until left >= pivot
			while (data.get(i) < pivot)
				i++;

			// Increment right pointer until right <= pivot
			while (data.get(j) > pivot)
				j--;

			// If left < right; swap values
			if (i <= j) {
				byte temp = data.get(i);
				data.put(i, data.get(j));
				data.put(j, temp);
				i++;
				j--;
			}

		}
		// quick_sort 'lesser values'
		quick_sort(data, left, j);

		// quick_sort 'greater values'
		quick_sort(data, i, right);
	}

}
